package class11;

import common.ArrayUtils;


/**
 * 机器人从起始位置，固定步数，走到目标位置的方式,有多少种？
 * 机器人走路问题
 * path: [1，2，3，4，5，6，7]
 * robot:   s     t
 * 说明：
 * 初始值：start=2, target=4, N=7, times=4
 * start:起始位置
 * target:目标位置
 * N:总共位置数
 * times: 走的步数
 * 更新：
 * 缓存法图解
 * * N = 7,  start = 2,  target = 4,  times = 4;
 * *   | 0  1  2  3  4    times = 4        | 0  1  2  3  4  依赖关系
 * * --|----------------------           --|---------------
 * * 0 | 0  0  0  0  0                   0 | 0  ↙  ↙  ↙  ↙
 * * 1 | 0  0  0  1  0                   1 | 0          ↖
 * * 2 | 0  0  1  0  4 start = 2         2 | 0           4
 * * 3 | 0  1  0  3  0                   3 | 0          ↙
 * * 4 | 1  0  2  0  0 target = 4        4 | 1
 * * 5 | 0  1  0  0  0                   5 | 0
 * * 6 | 0  0  0  0  0
 * * 7 | 0  0  0  0  0
 * * N = 7
 * <p>
 * *[1 2 3 4 5 6 7]
 * *   |   ^
 * * 2 1 2 3 4
 * * 2 3 2 3 4
 * * 2 3 4 3 4
 * * 2 3 4 5 4
 */
public class Code05_robotWay2 {
    public static void main(String[] args) {
        int start = 2, target = 4, N = 7, times = 4;
        int res = way2(start, target, N, times);
        System.out.println("res = " + res);
    }

    public static int way2(int start, int target, int N, int times) {
        // (N+1) * (times+1)
        int[][] dp = new int[N + 1][times + 1];
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < times + 1; j++) {
                dp[i][j] = 0;
            }
        }
        /**
         * cur 范围：1 ~ N
         * times范围：0 ~ times
         */
        int ans = process1(start, target, N, times, dp);
        ArrayUtils.printMatrixArr(dp);
        return ans;
    }

    /**
     * cur:机器人当前来的位置
     * rest: 剩余步数
     * target:最终目标
     * N:有哪些位置
     * 返回：机器人从cur出发，走过rest步之后，最终停在aim的方式数，是多少?
     */
    public static int process1(int cur, int target, int N, int rest, int[][] dp) {
        if (dp[cur][rest] != 0) {
            return dp[cur][rest];
        }
        int ans = 0;
        // 已经走到结尾，则返回
        if (rest == 0) {// 还剩下0步，则不需要再走
            ans = cur == target ? 1 : 0; // 如果刚好在target位置，则发现了一种路径
        } else if (cur == 1) {
            // 如果走到 1，只能往2方向走
            ans = process1(cur + 1, target, N, rest - 1, dp);
        } else if (cur == N) {// 如果走到 N，则只能往 N-1 方向走
            ans = process1(cur - 1, target, N, rest - 1, dp);
        } else {
            int l = process1(cur - 1, target, N, rest - 1, dp);
            int r = process1(cur + 1, target, N, rest - 1, dp);
            ans = l + r;
        }
        dp[cur][rest] = ans;
        return ans;

    }
}
